import lib.problem as problem
import unittest

X = 0
Y = 1

class Problem015(problem.Problem):
	def __init__(self):
		problem.Problem.__init__(self, 15)
		self.currentRoutesCount = 0
		self.routesCountForPos = {}
			
	def moveLeft(self, pos, n):
		if pos[X] == n:
			return None
		return (pos[X] + 1, pos[Y])
		
	def moveDown(self, pos, n):
		if pos[Y] == n:
			return None

		return (pos[X], pos[Y] + 1)
	
	def move(self, pos, n):
		
		if pos == (n, n):
			self.currentRoutesCount += 1
			return
		
		if pos in self.routesCountForPos:
			count = self.routesCountForPos[pos]

			self.currentRoutesCount += count
			return
		
		posLeft = self.moveLeft(pos, n)
		posDown = self.moveDown( pos, n)
		
		if 	posLeft:
			self.move(posLeft, n)
			
		if posDown:
			self.move(posDown, n)	
			
	
	def routeCountFromPos(self, fromPos, n):
		self.currentRoutesCount = 0
		self.move(fromPos, n)
		self.routesCountForPos[fromPos] = self.currentRoutesCount
		
		return self.currentRoutesCount
	
	
	def allRoutes(self, n):
		
		sequence = self.getBackwardsTriangleSequence( n)
		
		for pos in sequence:
			count = self.routeCountFromPos(pos, n)
			
		return count	
		
	
	
	def getBackwardsTriangleSequence(self, n):
		pos = (n, n)
		sequence = [pos] 
		
		while not pos == (0, 0):
			pos = self.getNextBackwardsTrianglePos(pos, n)
			sequence.append(pos)
			
		return sequence
	
	
	def getNextBackwardsTrianglePos(self, pos, n):
		
		if pos[Y] == 0:
			newPos = (0, pos[X] - 1)
		
		elif pos[X] == n:
			newPos = (pos[Y] - 1, n)
			
		else:
			newPos = (pos[X] + 1, pos[Y] - 1)
		
		return newPos 
	
	
	def solve(self):
		self.currentRoutesCount = 0
		self.routesCountForPos = {}
		return self.allRoutes(20)
	
	
class Problem015Tester(unittest.TestCase):
	
	def setUp(self):
		self.p015 = Problem015()
	
	def testRouteCountFromPos2(self):
		routes = self.p015.routeCountFromPos((0,0), 2)
		self.assertEquals(routes, 6)
		
	def testRouteCountFromPos7(self):
		routes = self.p015.routeCountFromPos((0,0), 7)
		self.assertEquals(3432, routes)
		
	def testConsecutiveRoutesCount(self):
		routes1 = self.p015.routeCountFromPos((3,3), 7)
		self.assertEquals(70, routes1)
		
		routes2 = self.p015.routeCountFromPos((0,0), 7)
		self.assertEquals(3432, routes2)
		
	def testAllRoutes7(self):
		routes = self.p015.allRoutes(7)
		self.assertEquals(3432, routes)
		
	def testAllRoutes2(self):
		routes = self.p015.allRoutes(2)
		self.assertEquals(6, routes)
		
	def testAllRoutes20(self):
		routes = self.p015.allRoutes(20)
		self.assertEquals(137846528820, routes)
		
	def testBackwardsTriangleSequence1(self):
		sequence = self.p015.getBackwardsTriangleSequence(1)
		expectedSequence = [(1,1),(0,1),(1,0),(0,0)]
		self.assertEquals(expectedSequence, sequence )
		
	def testBackwardsTriangleSequence2(self):
		sequence = self.p015.getBackwardsTriangleSequence(2)
		expectedSequence = [(2,2),(1,2),(2,1),(0,2),(1,1),(2,0),(0,1),(1,0),(0,0)]
		self.assertEquals(expectedSequence, sequence )
		
	def testSolve(self):
		count = self.p015.solve()
		self.assertEquals(137846528820, count )
	
